#!/usr/bin/env python
# encoding: utf-8
'''
@author: Excelsiorly
@license: (C) Copyright 2022, All Rights Reserved.
@contact: excelsiorly@qq.com
@file: 138. 复制带随机指针的链表.py
@time: 2022/3/3 13:05
@desc: https://leetcode-cn.com/problems/copy-list-with-random-pointer/
> 给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。
构造这个链表的深拷贝。深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。
例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。
返回复制链表的头节点。
用一个由n个节点组成的链表来表示输入/输出中的链表。每个节点用一个[val, random_index]表示：
    - val：一个表示Node.val的整数。
    - random_index：随机指针指向的节点索引（范围从0到n-1）；如果不指向任何节点，则为null。
你的代码 只 接受原链表的头节点 head 作为传入参数。

1. 迭代+哈希， Ot(N), Os(N)
2. 迭代，Ot(N), Os(1):
    1. 把新结点链到旧结点后面
    2. 通过旧结点的random，安排新结点的random（在旧random的下一个）
    3. 重连链表
'''
# Definition for a Node.
class Node:
    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
        self.val = int(x)
        self.next = next
        self.random = random


class Solution:
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        if not head: return None
        # hash1记录新旧结点对应关系，hash2记录新结点的random的旧位置
        hash1, hash2 = {}, {}
        dummy1, dummy2 = Node(-1), Node(-1)
        dummy1.next = head
        p, q = dummy1.next, dummy2
        while p:
            q.next = Node(p.val)
            q = q.next
            # 记录新旧结点
            hash1[p] = q
            # 记录random
            hash2[q] = p.random
            p = p.next

        q = dummy2.next
        while q:
            random = hash2[q]
            if random: q.random = hash1[random]
            q = q.next

        return dummy2.next


"""
# Definition for a Node.
class Node:
    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
        self.val = int(x)
        self.next = next
        self.random = random
"""


class Solution02:
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        if not head: return None

        # 把新结点链到旧结点后面
        p = head
        while p:
            next = p.next
            p.next = Node(p.val)
            p.next.next = next
            p = next

        # 通过旧结点的random，安排新结点的random（在旧random的下一个）
        p = head
        while p:
            random = p.random
            if random: p.next.random = random.next
            p = p.next.next
        # 重连链表
        p = head
        while p:
            new_node = p.next
            next = new_node.next
            if new_node.next: new_node.next = new_node.next.next
            p = next
        return head.next

if __name__ == '__main__':
    node1 = Node(7)
    node2 = Node(13)
    node3 = Node(11)
    node4 = Node(10)
    node5 = Node(1)
    node1.next, node1.random = node2, None
    node2.next, node2.random = node3, node1
    node3.next, node3.random = node4, node5
    node4.next, node4.random = node5, node3
    node5.random = node1
    head = node1
    res = Solution02().copyRandomList(head)
    print(res)